#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *prev; // 前驱指针
    struct Node *next; // 后继指针
} NODE;

// 初始化链表
NODE *initList()
{
    NODE *head = (NODE *)malloc(sizeof(NODE));

    if (head != NULL)
    {
        head->next = head;
        head->prev = head;
        // head->data = 0;
    }
    return head;
}

// 创建一个新的节点
NODE *createNode(int data)
{
    NODE *newNode = (NODE *)malloc(sizeof(NODE));

    if (newNode == NULL)
    {
        perror("内存创建失败！");
        return NULL;
    }

    newNode->data = data;
    newNode->prev = newNode;
    newNode->next = newNode;

    return newNode;
}

// 头插法
NODE *insertHead(NODE *head, int value)
{
    NODE *newNode = createNode(value);
    if (!newNode)
        return head;

    if (head == NULL)
        return newNode;

    newNode->next = head->next;
    newNode->prev = head;
    head->next->prev = newNode;
    head->next = newNode;

    return head;
}

// 显示链表,正向遍历
void displayList(NODE *head)
{
    if (head->next == head)
        return;
    NODE *p = head->next;
    do
    {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);

    printf("\n");
}

// 反向遍历
void reverse_display(NODE *head)
{
    if (head->prev == head)
        return;

    NODE *p = head->prev;
    do
    {
        printf("%d ", p->data);
        p = p->prev;
    } while (p != head);

    printf("\n");
}

// 在值为x的节点后插入一个值为y的新节点
NODE *insert(NODE *head, int x, int y)
{
    NODE *newNode = createNode(y);  //创建要插入的新节点     

    //若链表为空，直接在head后面插入新节点
    if (head->next == NULL)
    {
        head->next = newNode;
        newNode->next = head;
        head->prev = newNode;
        newNode->prev = head;

        return head;
    }
    
    NODE *p = head->next;

    //找值为x的节点，并把新节点插入到他的后面
    while (p != head)
    {
        if (p->data == x)
        {
            NODE *m = p->next;
            p->next = newNode;
            newNode->next = m;
            newNode->prev = p;
            m->prev = newNode;

            return head;
        }
        else
            p = p->next;
    }

    // 没有找到的话，插到末尾
    NODE *temp = head->prev;
    temp->next = newNode;
    newNode->prev = temp;

    newNode->next = head;
    head->prev = newNode;

    return head;
}

// 删除双向循环链表中所有值为x的节点
NODE *removeNode(NODE *head, int x)
{
    if (head->next == head)
        return NULL;

    NODE *p = head->next;
    while (p != head)
    {
        if (p->data == x)
        {
            if (p->next == head)
            {
                NODE *m = p->prev;
                m->next = head;
                head->prev = m;
                free(p);
                return head;
            }
            else
            {
                NODE *m = p->prev;
                NODE *temp = p;
                p = p->next;

                m->next = p;
                p->prev = m;
                free(temp);
            }
        }
        else
            p = p->next;
    }

    return head;
}

int main(int argc, char const *argv[])
{
    NODE *head = initList();

    // 头插法
    head = insertHead(head, 1);
    head = insertHead(head, 5);
    head = insertHead(head, 4);
    head = insertHead(head, 1);
    head = insertHead(head, 3);
    head = insertHead(head, 2);
    head = insertHead(head, 1);

    // 再值为5后面插入0
    head = insert(head, 7, 0);
    // head = insert(head,2,9);

    // 正向遍历
    displayList(head);
    // 反向遍历
    reverse_display(head);

    head = removeNode(head, 1);
    // head = removeNode(head,1);
    // head = removeNode(head,3);

    // 正向遍历
    displayList(head);
    // 反向遍历
    reverse_display(head);

    return 0;
}
